DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.40

FastMapSVM for Predicting CSP Satisfiability

Authors: Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

Recognizing the satisfiability of Constraint Satisfaction Problems (CSPs) is NP-hard. Although several Machine Learning (ML) approaches have attempted this task by casting it as a binary classification problem, they have had only limited success for a variety of challenging reasons. First, the NP-hardness of the task does not make it amenable to straightforward approaches. Second, CSPs come in various forms and sizes while many ML algorithms impose the same form and size on their training and test instances. Third, the representation of a CSP instance is not unique since the variables and their domain values are unordered. In this paper, we propose FastMapSVM, a recently developed ML framework that leverages a distance function between pairs of objects. We define a novel distance function between two CSP instances using maxflow computations. This distance function is well defined for CSPs of different sizes. It is also invariant to the ordering on the variables and their domain values. Therefore, our framework has broader applicability compared to other approaches. We discuss various representational and combinatorial advantages of FastMapSVM. Through experiments, we also show that it outperforms other state-of-the-art ML approaches.

Cite as

Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar. FastMapSVM for Predicting CSP Satisfiability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.CP.2023.40,
  author =	{Zheng, Kexin and Li, Ang and Zhang, Han and Kumar, T. K. Satish},
  title =	{{FastMapSVM for Predicting CSP Satisfiability}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.40},
  URN =		{urn:nbn:de:0030-drops-190775},
  doi =		{10.4230/LIPIcs.CP.2023.40},
  annote =	{Keywords: Constraint Satisfaction Problems, Machine Learning, FastMapSVM}
}

Document

Short Paper

DOI: 10.4230/LIPIcs.GIScience.2023.90

Visual Methods for Representing Flow Space with Vector Fields (Short Paper)

Authors: Han Zhang, Zhaoya Gong, and Jean-Claude Thill

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract

The issue of human mobility has been a focal point of research among numerous scholars in the field of geography for decades. Among them, the visualization of origin-destination (OD) data is an important branch of geographic flow studies. In this paper, we vectorize and represent immigration flows using OD flow data of U.S. immigrants in the year 2000, constructing an immigration space. Through data validation, it is confirmed that the vector field satisfies the Gauss’s theorem and is irrotational, demonstrating that the field can be derived from a potential and that the field is uniquely determined by the potential. Scalar potential fields are inferred from the vector field, providing a more intuitive and convenient description of the underlying flow patterns in geographical interaction matrices. Additionally, this paper employs potential fields and applies a density-equalizing areal cartogram to reconstruct the global representation of functional space, constructing cartogram maps based on potential magnitudes.

Cite as

Han Zhang, Zhaoya Gong, and Jean-Claude Thill. Visual Methods for Representing Flow Space with Vector Fields (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 90:1-90:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.GIScience.2023.90,
  author =	{Zhang, Han and Gong, Zhaoya and Thill, Jean-Claude},
  title =	{{Visual Methods for Representing Flow Space with Vector Fields}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{90:1--90:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.90},
  URN =		{urn:nbn:de:0030-drops-189852},
  doi =		{10.4230/LIPIcs.GIScience.2023.90},
  annote =	{Keywords: interstate migration, vector field, areal cartogram, geographic visualization}
}

Search Results

Documents authored by Zhang, Han

FastMapSVM for Predicting CSP Satisfiability

Abstract

Cite as

Visual Methods for Representing Flow Space with Vector Fields (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message